//目录：
// 1.冒泡排序 bubbleSort0   加标示符的冒泡排序bubbleSort00 原始人冒泡排序bubbleSort1  进化版冒泡排序bubbleSort2 升级版冒泡排序bubbleSort3
// 2.选择排序 selectionSort
// 3. 插入排序 insertSort
// 4. 希尔排序shellSort
// 5. 归并排序 mergeSort  merge
// 6.快速排序quickSort


// 1.  冒泡排序
// 　最优的时间复杂度为：O( n^2 ) ；//当使用标志位方法来判断你是否排好序时，时间复杂度为O(n)

// 最差的时间复杂度为：O( n^2 )；

// 平均的时间复杂度为：O( n^2 )；
// 1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。

// 2.第一轮的时候最后一个元素应该是最大的一个。

// 3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。
function bubbleSort0(arr) {
    var len = arr.length;
    for (var i = 0; i < len; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) { //相邻元素两两对比
                var temp = arr[j + 1]; //元素交换
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
// console.log("冒泡排序:" + bubbleSort0([3, 5, 2, 8, 9, 7, 6]));


// 加标示符的冒泡排序--时间复杂度为 O(n)
function bubbleSort00(arr) {
    var i = arr.length - 1; //初始时,最后位置保持不变
    while (i > 0) {
        var flag = 0; //每趟开始时,无记录交换
        for (var j = 0; j < i; j++)
            if (arr[j] > arr[j + 1]) {
                flag = j; //记录交换的位置,flag之后的均已交换成功
                var tmp = arr[j];　　　　　　　　　
                arr[j] = arr[j + 1];　　　　　　　　　
                arr[j + 1] = tmp;
            }
        i = flag; //为下一趟排序作准备，只要扫描到flag位置即可
    }
    return arr;
}



// 原始人冒泡排序
function bubbleSort1(arr) {　
    console.time('原始人冒泡排序耗时');　　
    var len = arr.length;　　
    for (var i = 0; i < len; i++) {　　　　
        for (var j = 0; j < len - 1 - i; j++) {　　　　　　
            if (arr[j] > arr[j + 1]) { //相邻元素两两对比
                　　　　　　　　
                var temp = arr[j + 1]; //元素交换
                　　　　　　　　
                arr[j + 1] = arr[j];　　　　　　　　
                arr[j] = temp;　　　　　　
            }　　　　
        }　　
    }
    console.timeEnd('原始人冒泡排序耗时');　　
    return arr;
}
// var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// console.log("原始人冒泡排序:" + bubbleSort1(arr));



// 进化版冒泡排序  --每次记录位置可以减少计算
function bubbleSort2(arr) {　　
    console.time('进化版冒泡排序耗时');　　
    var i = arr.length - 1; //初始时,最后位置保持不变　　
    　　
    while (i > 0) {　　　　
        var pos = 0; //每趟开始时,无记录交换
        　　　　
        for (var j = 0; j < i; j++) {　　　　　　
            if (arr[j] > arr[j + 1]) {　　　　　　　　
                pos = j; //记录交换的位置
                　　　　　　　　
                var tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;　　　　　　
            }　　　　
        }　　　　
        i = pos; //为下一趟排序作准备
        　　
    }　　
    console.timeEnd('进化版冒泡排序耗时');　　
    return arr;
}
// var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// console.log("进化版冒泡排序:" + bubbleSort2(arr)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] ；



// 升级版冒泡排序   --两头算双管齐下也能减少计算
function bubbleSort3(arr3) {　　
    var low = 0;　　
    var high = arr.length - 1; //设置变量的初始值
    　　
    var tmp, j;　　
    console.time('升级版冒泡排序耗时');　　
    while (low < high) {　　　　
        for (j = low; j < high; ++j) { //正向冒泡,找到最大者
            　　　　　　
            if (arr[j] > arr[j + 1]) {　　　　　　　　
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;　　　　　　
            }　　　　
        }　　　　--high; //修改high值, 前移一位
        　　　　
        for (j = high; j > low; --j) { //反向冒泡,找到最小者
            　　　　　　
            if (arr[j] < arr[j - 1]) {　　　　　　　　
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;　　　　　　
            }　　　　
        }　　　　　++low; //修改low值,后移一位
        　　
    }　　
    console.timeEnd('升级版冒泡排序耗时');　　
    return arr3;
}
// var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// console.log("升级版冒泡排序:" + bubbleSort3(arr)); //[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50] ;


// 自创版冒泡排序
function bubbleSort3(arr3) {　　
    var low = 0;　　
    var high = arr.length - 1; //设置变量的初始值
    　　
    var tmp, j;　　
    console.time('自创版冒泡排序耗时');　　
    while (low < high) {　　　　
        var pos1 = 0,
            pos2 = 0;　　　　
        for (let i = low; i < high; ++i) { //正向冒泡,找到最大者
            　　　　　　
            if (arr[i] > arr[i + 1]) {　　　　　　　　
                tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;　　　　　　　　
                pos1 = i;　　　　　　
            }　　　　
        }　　　　
        high = pos1; // 记录上次位置

        　　　　
        for (let j = high; j > low; --j) { //反向冒泡,找到最小者
            　　　　　　
            if (arr[j] < arr[j - 1]) {　　　　　　　　
                tmp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = tmp;　　　　　　　　　　
                pos2 = j;　　　　　　
            }　　　　
        }　　　　　　　　　　　
        low = pos2; //修改low值
        　　
    }　　
    console.timeEnd('自创版冒泡排序耗时');　　
    return arr3;
}
// var arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
// console.log("自创版冒泡排序:" + bubbleSort3(arr));




// 2.选择排序
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) { //寻找最小的数
                minIndex = j; //将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}
// console.log("选择排序:" + selectionSort([3, 5, 2, 8, 9, 7, 6]));




//3. 插入排序
function insertSort(arr) {
    var tmp;
    for (var i = 1; i < arr.length; i++) {
        tmp = arr[i];
        for (var j = i; j >= 0; j--) {
            if (arr[j - 1] > tmp) {
                arr[j] = arr[j - 1];
            } else {
                arr[j] = tmp;
                break;
            }
        }
    }
    return arr
}
// console.log("插入排序:" + insertSort([3, 5, 2, 8, 9, 7, 6]));




//4.希尔排序 --不必对很多元素进行交换
function shellSort(arr) {
    let temp,
        gap = 1;
    while (gap < arr.length / 3) {
        gap = gap * 3 + 1 //动态定义间隔序列
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) { //控制步长（间隔）并不断缩小
        for (var i = gap; i < arr.length; i++) { //按照增量个数对序列进行排序
            temp = arr[i]
            for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) { //例：j=0  arr[1]>arr[5]
                arr[j + gap] = arr[j]
            }
            arr[j + gap] = temp
        }
    }
    return arr
}




//5. 归并排序
function mergeSort(arr) {
    if (arr.length < 2) {
        return arr;
    }
    //将数组分为左右两个子序列
    let middle = Math.floor(arr.length / 2)
    let left = arr.slice(0, middle)
    let right = arr.slice(middle)
    return merge(mergeSort(left), mergeSort(right)) //对两个子序列重复划分为两个进行排序，直到不能划分
}

function merge(left, right) {
    let result = []
    while (left.length > 0 && right.length > 0) {
        if (left[0] < right[0]) { //两两比较，较小的放入结果数组
            result.push(left.shift()) //shift()方法删除数组第一个元素，并返回被删除的元素
        } else {
            result.push(right.shift())
        }
    }
    /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
    return result.concat(left).concat(right);
}


//   6.快速排序
function quickSort(arr) {
    //如果数组<=1,则直接返回
    if (arr.length <= 1) { return arr; }
    var pivotIndex = Math.floor(arr.length / 2);
    //找基准，并把基准从原数组删除
    var pivot = arr.splice(pivotIndex, 1)[0];
    //定义左右数组
    var left = [];
    var right = [];

    //比基准小的放在left，比基准大的放在right
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] <= pivot) {
            left.push(arr[i]);
        } else {
            right.push(arr[i]);
        }
    }
    //递归
    return quickSort(left).concat([pivot], quickSort(right));
}